package QueuePractice;

import java.util.LinkedList;
import java.util.Queue;

public class IsLandNumBFS {
    /**
     * 岛屿数量
     * 给你一个由1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     * <p>
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     * <p>
     * 此外，你可以假设该网格的四条边均被水包围。
     * <p>
     * 示例 1：
     * <p>
     * 输入：grid = [
     * ["1","1","1","1","0"],
     * ["1","1","0","1","0"],
     * ["1","1","0","0","0"],
     * ["0","0","0","0","0"]
     * ]
     * 输出：1
     * 示例 2：
     * <p>
     * 输入：grid = [
     * ["1","1","0","0","0"],
     * ["1","1","0","0","0"],
     * ["0","0","1","0","0"],
     * ["0","0","0","1","1"]
     * ]
     * 输出：3
     */
    public int numIslands(char[][] grid) {
        if(grid==null || grid.length==0){
            return 0;
        }
        int col = grid.length;
        int row = grid[0].length;

        int numIsLand = 0;
        for (int i = 0; i < col; i++) {
            for (int j = 0; j < row; j++) {
                if (grid[i][j] == '1') {
                    numIsLand++;
                    //如果当前位置是1，那么使用广度优先搜索判断上下左右是否是1。
                    bfs(grid, i, j);
                }
            }
        }
        return numIsLand;
    }

    private void bfs(char[][] grid, int i, int j) {
        grid[i][j] = '0';
        int col = grid.length;
        int row = grid[0].length;
        Queue<Integer> queue = new LinkedList<>();
        //i * col + j当前的位置转化成一维的数字
        queue.offer(i * row + j);
        while (!queue.isEmpty()) {
            int position = queue.poll();
            int c = position / row;
            //3%3=0
            int r = position % row;
            //上面
            if (c > 0 && grid[c - 1][r] == '1') {
                queue.offer((c - 1) * row + r);
                grid[c - 1][r] = '0';
            }
            if (c < col - 1 && grid[c + 1][r] == '1') {
                queue.offer((c + 1) * row + r);
                grid[c + 1][r] = '0';
            }
            //左边
            if (r > 0 && grid[c][r - 1] == '1') {
                queue.offer(c * row + r - 1);
                grid[c][r - 1] = '0';
            }
            if (r < row - 1 && grid[c][r + 1] == '1') {
                queue.offer(c * row + r + 1);
                grid[c][r + 1]='0';
            }

        }
    }
}
